#pragma once

#include "CachePolicy.h"

#include <cmath>
#include <cstdio>
#include <iostream>
#include <memory>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <vector>

namespace Cache {

template <typename Key, typename Value>
class LfuCache;

template <typename Key, typename Value>
class LfuKCache;

template <typename Key, typename Value>
class FreqList {
  private:
    struct Node {
        int freq;
        Key key;
        Value val;
        std::weak_ptr<Node> prev;
        std::shared_ptr<Node> next;

        Node() : freq(1), next(nullptr) {}
        Node(Key key, Value val) : freq(1), key(key), val(val), next(nullptr) {}
    };

  private:
    using NodePtr = std::shared_ptr<Node>;

  private:
    int freq_;
    NodePtr dummyHead_;
    NodePtr dummyTail_;

  public:
    explicit FreqList(const int n) : freq_(n) {
        dummyHead_ = std::make_shared<Node>();
        dummyTail_ = std::make_shared<Node>();
        dummyHead_->next = dummyTail_;
        dummyTail_->prev = dummyHead_;
    }

    [[nodiscard]] bool isEmpty() const { return dummyHead_->next == dummyTail_; }

    void addNode(NodePtr node) {
        if (!node || !dummyHead_ || !dummyTail_)
            return;

        node->prev = dummyTail_->prev;
        node->next = dummyTail_;
        dummyTail_->prev.lock()->next = node;
        dummyTail_->prev = node;
    }

    void removeNode(NodePtr node) {
        if (!node || !dummyHead_ || !dummyTail_)
            return;
        if (node->prev.expired() || !node->next)
            return;

        auto prev = node->prev.lock();
        prev->next = node->next;
        node->next->prev = prev;
        node->next = nullptr;
    }

    NodePtr getFirstNode() const { return dummyHead_->next; }

  public:
    friend class LfuCache<Key, Value>;
    friend class LfuKCache<Key, Value>;
};

template <typename Key, typename Value>
class LfuCache : public CachePolicy<Key, Value> {
  private:
    //! typename 告诉编译器 FreqList<Key, Value>::Node 是一个类型，而不是变量
    using Node = typename FreqList<Key, Value>::Node;
    using NodePtr = std::shared_ptr<Node>;
    using NodeMap = std::unordered_map<Key, NodePtr>;

  public:
    explicit LfuCache(const int capacity) : capacity_(capacity) {}

    ~LfuCache() override = default;

    void put(Key key, Value val) override {
        if (capacity_ == 0)
            return;

        std::lock_guard<std::mutex> lock(mtx_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end()) {
            it->second->val = val;
            getInternal(it->second, val);
            return;
        }

        putInternal(key, val);
    }

    bool get(Key key, Value &val) override {
        std::lock_guard<std::mutex> lock(mtx_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end()) {
            getInternal(it->second, val);
            return true;
        }

        return false;
    }

    Value get(Key key) override {
        Value val{};
        get(key, val);
        return val;
    }

    void purge() {
        minFreq_ = 0;
        nodeMap_.clear();
        freq2FreqList_.clear();
    }

  private:
    void putInternal(Key key, Value val) {
        if (nodeMap_.size() == capacity_)
            kickOut();

        NodePtr node = std::make_shared<Node>(key, val);
        nodeMap_[key] = node;
        addToFreqList(node);
        minFreq_ = 1;
    }

    void getInternal(NodePtr node, Value &val) {
        val = node->val;
        removeFromFreqList(node);
        ++node->freq;
        addToFreqList(node);
        minFreq_ = std::min(minFreq_, node->freq);
    }

    void kickOut() {
        NodePtr node = freq2FreqList_[minFreq_]->getFirstNode();
        removeFromFreqList(node);
        nodeMap_.erase(node->key);
    }

    void removeFromFreqList(NodePtr node) {
        if (!node)
            return;

        auto freq = node->freq;
        freq2FreqList_[freq]->removeNode(node);
    }

    void addToFreqList(NodePtr node) {
        if (!node)
            return;

        auto freq = node->freq;
        if (freq2FreqList_.find(freq) == freq2FreqList_.end())
            freq2FreqList_[freq] = std::make_shared<FreqList<Key, Value>>(freq);

        freq2FreqList_[freq]->addNode(node);
    }

  private:
    int minFreq_{0};
    int capacity_;
    std::mutex mtx_;
    NodeMap nodeMap_;
    std::unordered_map<int, std::shared_ptr<FreqList<Key, Value>>> freq2FreqList_;  // 访问频次到该频次链表的映射
};

template <typename Key, typename Value>
class LfuKCache : public CachePolicy<Key, Value> {
  private:
    using Node = typename FreqList<Key, Value>::Node;
    using NodePtr = std::shared_ptr<Node>;
    using NodeMap = std::unordered_map<Key, NodePtr>;

  public:
    explicit LfuKCache(const int capacity, const int maxAvgNum = 100)
        : capacity_(capacity), minFreq_(INT8_MAX), maxAvgNum_(maxAvgNum), curAvgNum_(0), curTotalNum_(0) {}

    ~LfuKCache() override = default;

    void put(Key key, Value val) override {
        if (capacity_ == 0)
            return;

        std::lock_guard<std::mutex> lock(mtx_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end()) {
            it->second->val = val;
            getInternal(it->second, val);
            return;
        }

        putInternal(key, val);
    }

    bool get(Key key, Value &val) override {
        std::lock_guard<std::mutex> lock(mtx_);
        auto it = nodeMap_.find(key);
        if (it != nodeMap_.end()) {
            getInternal(it->second, val);
            return true;
        }

        return false;
    }

    Value get(Key key) override {
        Value val{};
        get(key, val);
        return val;
    }

    void purge() {
        nodeMap_.clear();
        freq2FreqList_.clear();
    }

  private:
    void putInternal(Key key, Value val) {
        if (nodeMap_.size() == capacity_)
            kickOut();

        NodePtr node = std::make_shared<Node>(key, val);
        nodeMap_[key] = node;
        addToFreqList(node);
        addFreqNum();
        minFreq_ = std::min(1, minFreq_);
    }

    void getInternal(NodePtr node, Value &val) {
        val = node->val;
        removeFromFreqList(node);
        ++node->freq;
        addToFreqList(node);
        if (node->freq - 1 == minFreq_ && freq2FreqList_[node->freq - 1]->isEmpty())
            ++minFreq_;

        addFreqNum();
    }

    void kickOut() {
        NodePtr node = freq2FreqList_[minFreq_]->getFirstNode();
        removeFromFreqList(node);
        nodeMap_.erase(node->key);
        decreaseFreqNum(node->freq);
    }

    void removeFromFreqList(NodePtr node) {
        if (!node)
            return;
        auto freq = node->freq;
        freq2FreqList_[freq]->removeNode(node);
    }

    void addToFreqList(NodePtr node) {
        if (!node)
            return;
        auto freq = node->freq;
        if (freq2FreqList_.find(freq) == freq2FreqList_.end())
            freq2FreqList_[freq] = new FreqList<Key, Value>(freq);

        freq2FreqList_[freq]->addNode(node);
    }

    void addFreqNum() {
        ++curAvgNum_;
        if (nodeMap_.empty())
            curAvgNum_ = 0;
        else
            curAvgNum_ = curTotalNum_ / nodeMap_.size();

        if (curAvgNum_ > maxAvgNum_)
            handleOverMaxAverageNum();
    }

    void decreaseFreqNum(int num) {
        curTotalNum_ -= num;
        if (nodeMap_.empty())
            curAvgNum_ = 0;
        else
            curAvgNum_ = curTotalNum_ / nodeMap_.size();
    }

    void handleOverMaxAverageNum() {
        if (nodeMap_.empty())
            return;

        for (auto it = nodeMap_.begin(); it != nodeMap_.end(); ++it) {
            if (!it->second)
                continue;

            NodePtr node = it->second;
            removeFromFreqList(node);

            node->freq -= maxAvgNum_ / 2;
            node->freq = node->freq < 1 ? 1 : node->freq;

            addToFreqList(node);
        }

        updateMinFreq();
    }

    void updateMinFreq() {
        minFreq_ = INT8_MAX;
        for (const auto &pair : freq2FreqList_) {
            if (pair.second && !pair.second->isEmpty())
                minFreq_ = std::min(minFreq_, pair.first);
        }

        if (minFreq_ == INT8_MAX)
            minFreq_ = 1;
    }

  private:
    int capacity_;
    int minFreq_;
    int maxAvgNum_;
    int curAvgNum_;
    int curTotalNum_;
    std::mutex mtx_;
    NodeMap nodeMap_;
    std::unordered_map<int, FreqList<Key, Value> *> freq2FreqList_;
};

template <typename Key, typename Value>
class HashLfuCaches : public CachePolicy<Key, Value> {
  public:
    HashLfuCaches(size_t capacity, int sliceNum, int maxAvgNum = 10)
        : sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency()), capacity_(capacity) {
        size_t sliceSize = std::ceil(capacity_ / static_cast<double>(sliceNum_));
        for (int i = 0; i < sliceNum_; ++i)
            lfuSliceCaches_.emplace_back(new LfuKCache<Key, Value>(sliceSize, maxAvgNum));
    }

    void put(Key key, Value val) override {
        size_t sliceIdx = Hash(key) % sliceNum_;
        lfuSliceCaches_[sliceIdx]->put(key, val);
    }

    bool get(Key key, Value &val) override {
        size_t sliceIdx = Hash(key) % sliceNum_;
        return lfuSliceCaches_[sliceIdx]->get(key, val);
    }

    Value get(Key key) override {
        Value val;
        get(key, val);
        return val;
    }

    void purge() {
        for (auto &lfuCache : lfuSliceCaches_)
            lfuCache->purge();
    }

  private:
    size_t Hash(Key key) {
        std::hash<Key> hashFunc;
        return hashFunc(key);
    }

  private:
    int sliceNum_{0};
    size_t capacity_{0};
    std::vector<std::unique_ptr<LfuKCache<Key, Value>>> lfuSliceCaches_;
};

}  // namespace Cache